#include <stdio.h>
#include <stdlib.h>

#include "link_tree.h"
#include "link_queue.h"
#include "link_stack.h"

char* str;

TreeNode* create_lt()
{
    if(NULL == str || '#' == *str)return NULL;
    TreeNode * tree = create_tn(str,0);
    tree->left = create_lt(++str);
    tree->right = create_lt(++str);
    return tree;
}

void destory_lt(TreeNode* root){
    if(NULL == root) return;
    destory_lt(root->left);
    free(root->data);
    destory_lt(root->right);
    free(root);
}

void dlr_lt(TreeNode* node,FUNC show)
{
    if(NULL == node)
        return;
    show(node->data);
    //printf("%c ",node->data);
    dlr_lt(node->left,show);
    dlr_lt(node->right,show);
}

void ldr_lt(TreeNode* node,FUNC show)
{
    if(NULL == node) return;
    ldr_lt(node->left,show);
    show(node->data);
    ldr_lt(node->right,show);
}

void lrd_lt(TreeNode* node,FUNC show)
{
    if(NULL == node)
        return;
    lrd_lt(node->left,show);
    lrd_lt(node->right,show);
    show(node->data);
}
//树的密度
size_t density_lt(TreeNode* node)
{
    if(NULL == node)
        return 0;
    return density_lt(node->left) + density_lt(node->right) + 1;
}
//树的高度
size_t height_lt(TreeNode* node)
{
    if(NULL == node)
        return 0;
    size_t l = height_lt(node->left);
    size_t r = height_lt(node->right);
    return l>r?l+1:r+1;
}
//判断树平衡
bool balance_lt(TreeNode* node)
{
    if(NULL == node)
        return true;
    int l = height_lt(node->left);
    int r = height_lt(node->right);
    return 1 >= abs(l-r) && balance_lt(node->left) && balance_lt(node->right);
}

TreeNode* create_dlr2lt(char* dlr, char* ldr, size_t len)
{
    if(0 == len) return NULL;
    TreeNode* tree = create_tn(dlr,0);
    int index = 0;
    while(*(ldr + index) != *(char*)tree->data)index++;
    //printf("%d\n",index);
    tree->left = create_dlr2lt(dlr+1,ldr,index);
    tree->right = create_dlr2lt(dlr+1+index,ldr+index+1,len-1-index);
    return tree;
}

TreeNode* create_lrd2lt(char* lrd, char* ldr, size_t len)
{
    if(0 == len)
        return NULL;
    TreeNode* tree = create_tn(lrd + len,0);
    int index = len - 1;
    while(*(ldr + index) != *(char*)tree->data)
        index++;
    //printf("%d\n",index);
    tree->left = create_lrd2lt(lrd+1,ldr+index+1,index);
    tree->right = create_lrd2lt(lrd+1+index,ldr,len-1-index);
    return tree;
}

void lv_lt(TreeNode* node,FUNC show)
{
    LinkQueue *queue = create_lq();
    if(NULL != node)
        push_lq(queue,node);
    while(!empty_lq(queue))
    {
        TreeNode *n = front_lq(queue);
        show(n->data);
        if(NULL != n->left)
            push_lq(queue,n->left);
        if(NULL != n->right)
            push_lq(queue,n->right);
        pop_lq(queue);
    }
    destory_lq(queue);
}

void mirror_lt(TreeNode* tree)
{
    if(NULL == tree)return;
    TreeNode* tmp = tree->left;
    tree->left = tree->right;
    tree->right = tmp;
    mirror_lt(tree->left);
    mirror_lt(tree->right);
}

bool check_child_lt(TreeNode* child, TreeNode* father)
{
    if(NULL == father) return true;
    if(NULL == child) return false;
    //printf("%c %c\n",child->data,father->data);
    return child->data == father->data &&
           check_child_lt(child->left,father->left) &&
           check_child_lt(child->right,father->right);

}

bool is_child_lt(TreeNode* child, TreeNode* father)
{
    if(NULL == father || NULL == child)return false;
    bool flag = false;
    if(child->data == father->data){
        flag = check_child_lt(child,father);
    }
    return flag || is_child_lt(child,father->left) || is_child_lt(child,father->right);
}

void _ldr_lt(TreeNode* tree,TreeNode** res)
{
    if(NULL == tree)return;
    _ldr_lt(tree->left,res);
    if(NULL == *res)*res = tree;
    _ldr_lt(tree->right,res);
}

TreeNode* first_ldr_lt(TreeNode* tree)
{
//    if(NULL == tree)return NULL;
//    if(NULL == tree->left){
//        if(NULL == tree->right) return tree;
//        return first_ldr_lt(tree->right);
//    }
//    return first_ldr_lt(tree->left);
    TreeNode* res = NULL;
    _ldr_lt(tree,&res);
    return res;
}

bool _is_symmetry_lt(TreeNode* left,TreeNode* right)
{
    if(NULL == left && NULL == right)return true;
    if(NULL == left || NULL == right)return false;
    return left->data == right->data &&
            _is_symmetry_lt(left->right,right->left) &&
            _is_symmetry_lt(left->left,right->right);
}

bool is_symmetry_lt(TreeNode* tree)
{
    if(NULL == tree)return true;
    return _is_symmetry_lt(tree->left,tree->right);
}

void zhi_lt(TreeNode* tree,bool direction,FUNC show)
{
    if(NULL == tree)return;
    LinkStack *s1 = create_ls();
    LinkStack *s2 = create_ls();
    push_ls(s1,tree);
    while(!empty_ls(s1) || !empty_ls(s2)){
        //谁空谁当下一层的暂存
        LinkStack *sin = empty_ls(s1)?s1:s2;
        LinkStack *sout = empty_ls(s1)?s2:s1;
        while(!empty_ls(sout)){
            TreeNode* tmp = top_ls(sout);
            show(tmp->data);
            pop_ls(sout);
            if(direction){
                if(NULL != tmp->left)push_ls(sin,tmp->left);
                if(NULL != tmp->right)push_ls(sin,tmp->right);
            }else{
                if(NULL != tmp->right)push_ls(sin,tmp->right);
                if(NULL != tmp->left)push_ls(sin,tmp->left);
            }
        }
        direction = !direction;
    }
}
